package 中等.动态规划.其他;

import java.util.*;

/**
 * 你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，
 * 你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。
 * 乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi]
 * 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。
 * 每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。
 * 给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。
 * 注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。
 *
 * @author xudongfu
 * @date 2023/12/08
 */
public class 出租车的最大盈利_2008 {

    public static void main(String[] args) {

        System.out.println(maxTaxiEarnings(5, new int[][]{{2, 5, 4}, {1, 5, 1}}));

    }

    /**
     * 动态规划
     * 1，子问题
     * dp[i] 表示 [1,i] 个地点最多能盈利多少元
     * 2，状态转移方程
     * a 第 i 个地点，没有接乘客的情况
     * dp[i] = dp[i-1]
     * b 第 i 个地点，接乘客，从 rides 中选择 endi = i 中
     * 盈利最多的那一个
     */
    public static long maxTaxiEarnings(int n, int[][] rides) {
        long[] dp = new long[n + 1];

        Arrays.sort(rides, (a, b) -> a[1] - b[1]);

        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] ride : rides) {
            List<int[]> list = map.get(ride[1]);
            if (list == null) {
                list = new ArrayList<>();
                map.put(ride[1], list);
            }
            list.add(ride);
        }

        for (int i = 1; i <= n; i++) {
            // 不选
            dp[i] = dp[i - 1];
            // 选一个以 endi 结尾最大收益的乘客
            List<int[]> list = map.get(i);
            if (list == null) {
                continue;
            }
            for (int[] ride : list) {
                dp[i] = Math.max(dp[i], dp[ride[0]] + (ride[1] - ride[0]) + ride[2]);
            }
        }
        return dp[n];
    }
}
